An integrated circuit (“IC”) is a semiconductor device that includes many electronic components (e.g., transistors, diodes, inverters, etc.). These electrical components are interconnected to form larger scale circuit components (e.g., gates, cells, memory units, arithmetic units, controllers, decoders, etc.) on the IC. The electronic and circuit components of IC's are jointly referred to below as “components.”
An IC also includes multiple layers of metal and/or polysilicon wiring that interconnect its electronic and circuit components. For instance, many IC's are currently fabricated with five metal layers. In theory, the wiring on the metal layers can be all-angle wiring (i.e., the wiring can be in any arbitrary direction). Such all-angle wiring is commonly referred to as Euclidean wiring. In practice, however, each metal layer typically has a preferred wiring direction in an attempt to maximize the number of signal wires placed on each wiring layer by preventing intersections. In current ICs, the preferred direction alternates between successive metal layers. Most IC's use the “Manhattan” wiring model, which specifies alternating layers of preferred-direction horizontal and vertical wiring. (Viewed from above, the horizontal and vertical wiring resemble the orthogonal streets of Manhattan.) In the Manhattan wiring model, essentially all of the interconnect wires are horizontal or vertical.
Design engineers design IC's by transforming circuit description of the IC's into geometric descriptions, called layouts. To create an integrated circuit layout, design engineers typically use electronic design automation (“EDA”) applications. These EDA applications provide sets of computer-based tools for creating, editing; and analyzing IC design layouts. EDA applications create layouts by using geometric shapes that represent different materials and devices on IC's. For instance, EDA tools commonly use rectangular lines to represent the wire segments that interconnect the IC components. These EDA tools also represent electronic and circuit IC components as geometric objects with varying shapes and sizes. For the sake of simplifying the discussion, these geometric objects are shown as rectangular blocks in this document. Also, in this document, the geometric representation of an electronic or circuit IC component by an EDA application is referred to as a “circuit module.”
EDA applications typically illustrate circuit modules with electrical interface “pins” on the sides of the circuit modules. These pins connect to the interconnect lines, the “wiring” used to connect the various circuit modules. A collection of pins that are, or need to be, electrically connected is referred to as a net.
FIG. 1 illustrates a simple example of an IC layout 100. The IC layout 100 includes five circuit modules 105, 110, 115, 120, and 125 with pins 130-160. Four interconnect lines 165-180 connect these modules through their pins. In addition, five nets specify the interconnection between the pins. Specifically, pins 35, 45, and 60 define a three-pin net, while pins 30 and 55, and pins 40 and 50 respectively define two two-pin nets. As shown in FIG. 1, a circuit module (such as 105) can have multiple pins on multiple nets.
The IC design process entails various operations. FIG. 2 illustrates the overall process for laying out an integrated circuit device once the logical circuit design of the integrated circuit device has been completed. Some of the physical-design operations that EDA applications commonly help perform to layout an integrated circuit include: (1) floor planning (in step 210 of FIG. 2), which divides the integrated circuit layout area into different sections devoted to different purposes (such as ALU, memory, decoding, etc.); (2) placement (in step 220 of FIG. 2), which finds the alignment and relative orientation of the circuit modules; (3) global and detailed routing (in steps 230 and 240 of FIG. 2), which completes the interconnects between the circuit modules as specified by the net list; (4) compaction (in step 250 of FIG. 2), which compresses the layout in all directions to decrease the total IC area; and (5) verification (in step 250 of FIG. 2), which checks the layout to ensure that it meets design and functional requirements.
Referring to step 210 of FIG. 2, layout designers initially perform high-level floor planning. During the high-level floor planning, layout designers decide roughly where various large circuit blocks will be placed on the integrated circuit. The layout designers then perform a “placement” step 220. During the placement step, the layout designers place all the circuit cells into specific locations while following the high-level floor planning map of step 210. The placement step 220 is largely performed with the help of EDA tools that help select optimized placement. FIG. 3a illustrates an example of two large circuit modules 310 and 320 and two smaller circuit modules 330 and 340 placed onto an integrated circuit layout. The various circuit modules may be rotated ninety degrees as necessary to obtain a desired layout.
Operation (3), routing, is generally divided into two sub steps: global routing (step 230 of FIG. 2) and detailed routing (step 240 of FIG. 2). Global routing divides an integrated circuit into individual global routing areas. Then, a global routing path is created for each net by listing the global routing areas that the net must pass through. After global routes have been created, each individual global routing area is then processed with detailed routing. Detailed routing creates specific individual routing paths for each net within that global routing area.
Global routing is a step that is used to divide an extremely difficult overall routing problem into smaller routing problems in a “divide and conquer” approach. The overall task of routing an integrated circuit is to route together all electrically common signals on the integrated circuit. The global routing step divides an integrated circuit area into individual global routing areas and then determines the specific global routing areas that each electrically common signal must pass through. The list of circuit modules and pins that need to be connected for a specific electrically common signal is known as a net. The contiguous path through the global routing areas is known as a “global routing path” for that net. An example of global routing is provided with reference to FIGS. 3a and 3b. 
Referring to FIG. 3a, there are three different electrically common signals A, B, and C. The electrical signal terminations for electrically common signals A, B, and C illustrated on FIG. 3a as marked dots. The electrical signal terminations are commonly referred to as “pins”. Furthermore, the integrated circuit of FIG. 3a has been divided into sixteen different global routing areas that are labeled 01 to 16. For each electrically common signal, a net is created containing a list of all the global routing areas that have common electrical signal termination pins. Thus, for example, the net of electrical signal A is 01, 02, 08, and 12 since electrical signal A has termination pins in those labeled global routing areas.
After creating the various nets, global routing path lists are then constructed from the various nets. FIG. 3b illustrates the integrated circuit of FIG. 3a with the addition of global routing path lists and roughly sketched global routing paths. (The actual specific routing path is not determined during the global routing step, just the list of global routing areas that a signal must enter or pass through.) The global routing paths join together global routing areas in the nets with additional global routing areas such that all global routing areas in the global routing path list form a contiguous global routing path. Note that each net may have many different possible global routing paths. The Electronic Design Automation (EDA) software attempts to select the global routing paths that are close to optimal.
Referring back to the flow diagram of FIG. 2, detailed routing is performed at step 240 for the various global routing areas. In the detailed routing process, each electrical interconnect signal line that passes through or terminates within a particular global routing area must be given a specific routing path within that global routing area. Generally, detailed routing systems use a routing grid that specifies a very limited set of possible locations for the various electrical interconnect signals. Adjacent electrical interconnect signals in a gridded detailed routing system are separated by a worst-case distance that will ensure that adjacent electrical interconnect signals are not shorted together during the manufacturing process.
The routing example illustrated in FIGS. 3a and 3b requires several detailed routing tasks to be performed. For example, the detailed routing for global routing area 06 requires that electrical interconnect signal B pass from the left side to the right side of the global routing area and electrical interconnect signal C enter from the bottom and terminate at a pin on large circuit module 310. FIG. 3c illustrates an example of one possible detailed route for global routing area 06. Note that the detailed electrical interconnect signal routes illustrated in FIG. 3c follow the prescribed routing grid that is illustrated with dashed lines. The vertical and horizontal interconnect lines are on different layers such that there is no electrical connection at places where the interconnect wires cross unless a via has been created at that location. In most cases, many different possible detailed routing paths exist. For example, FIG. 3d illustrates just one alternate detailed electrical interconnect signal routing for global routing area 06 of the layout illustrated in FIGS. 3a and 3b. 
Since the global routing step 230 divided the overall routing problem into many smaller routing problems, the detailed routing of each individual global routing area is simplified. If a particular detailed routing problem is unsolvable, the system may return to step 230 in order to get a different global routing solution and then attempt detailed routing on the new global routing solution. Thus, routing an integrated circuit is often an iterative process.
Referring back to FIG. 2, after the routing steps have been performed, the integrated circuit layout is tested and optimized at step 250. Common testing and optimization steps include extraction, verification, and compaction. The steps of extraction and verification are performed to ensure that the integrated circuit layout will perform as desired. Compaction allows designers to reduce the size of an integrated circuit design in order to improve performance. Furthermore, a compacted design lowers costs by allowing more integrated circuits to be produced for a given wafer size. Finally, the tested and optimized integrated circuit is manufactured at step 290. Note that problems may occur during various steps of the integrated circuit layout forcing the designers to return to earlier steps.
The task of routing a typical integrated circuit is a very difficult task due to the large number of interconnect lines that must be routed and the extremely large number of possible different routing paths. To simplify the routing task, most automated routing systems use a gridded system wherein the number of possible positions of interconnect signals is sharply limited to a specific set wiring grid. However, a gridless routing system that allows interconnect signal wires to be placed anywhere can provide better routing since it is not limited by the artificial routing grid restriction. Thus, to provide highly optimized interconnect line routing, it is desirable to implement gridless integrated circuit architectures.